#!/usr/bin/env python

#Copyright (C) 2008 Luis Felipe Millani (lf.millani@gmail.com)

#This file is part of MagicLyrics.

#MagicLyrics is free software: you can redistribute it and/or modify
#it under the terms of the GNU General Public License as published by
#the Free Software Foundation, either version 3 of the License, or
#(at your option) any later version.

#MagicLyrics is distributed in the hope that it will be useful,
#but WITHOUT ANY WARRANTY; without even the implied warranty of
#MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#GNU General Public License for more details.

#You should have received a copy of the GNU General Public License
#along with MagicLyrics.  If not, see <http://www.gnu.org/licenses/>.

'''
	try to change if (j if index_in_a else i) not in t[j-1]:
	into if t[-1][-1]!=(j if index_in_a else i)
'''

'''
def lcs_recursive(a,b):
	"""
	does the same as lcs(), albeit (much) slower
	it's here only because it's easier to understand
	"""
	if len(a)==0 or len(b)==0:return []
	best=lcs_recursive(a[:-1],b)
	p=lcs_recursive(a,b[:-1])
	if len(best)<len(p):
		best=p
	p=lcs_recursive(a[:-1],b[:-1])
	if a[-1:]==b[-1:] and len(best)<len(p)+1:
		best=p
		best.extend(a[-1:])
	return best
'''
def lcs(a,b,index_in_a=True):
	"""
	lcs(...) -> list of int
	
	return a list of indexes in a (or b) corresponding to the longest
	common subsequence between a and b
	
	a			list / string
	b			list / string
	index_in_a	boolean; True returns indexes in a, False, in b
	"""
	if a>b:return lcs(b,a,not index_in_a) # since we allocate len(a) lists and we don't want to waste memory, len(a) should be <= len(b)
	
	t=[]
	lens=[] # checking lens[i] is faster than len(t[i])
	for i in xrange(len(a)):(t.append([]),lens.append(0))
	
	for i in xrange(len(b)):
		if lens[0]==0 and b[i]==a[0]:
			t[0].append(0 if index_in_a else i)
			lens[0]=1
		for j in xrange(1,len(a)):
			if lens[j-1]==lens[j]:
				if b[i]==a[j]:
					if (j if index_in_a else i) not in t[j-1]:
						t[j]=[]
						t[j].extend(t[j-1])
						t[j].append((j if index_in_a else i))
						lens[j]+=1
			elif lens[j-1]>lens[j]:
				t[j]=[]
				t[j].extend(t[j-1])
				lens[j]=lens[j-1]
	return t[-1]
def lcs0(a,b,index_in_a=True):
	"""
	lcs(...) -> list of int
	
	return a list of indexes in a (or b) corresponding to the longest
	common subsequence between a and b
	
	a			list / string
	b			list / string
	index_in_a	boolean; True returns indexes in a, False, in b
	"""
	if a>b:return lcs(b,a,not index_in_a) # since we allocate len(a) lists and we don't want to waste memory, len(a) should be <= len(b)
	
	t=[]
	lens=[] # checking lens[i] is faster than len(t[i])
	for i in xrange(len(a)):(t.append([]),lens.append(0))
	
	for i in xrange(len(b)):
		if lens[0]==0 and b[i]==a[0]:
			t[0].append(0 if index_in_a else i)
			lens[0]=1
		for j in xrange(1,len(a)):
			if lens[j-1]==lens[j]:
				if b[i]==a[j]:
					#if ((j if index_in_a else i) not in t[j-1])!=(len(t[j-1])==0 or (t[j-1][-1]!=(j if index_in_a else i))):
					#	print j if index_in_a else i
					#	print t[j-1]
					#	print t[-1][-1]
					#	print (j if index_in_a else i) not in t[j-1],len(t[j-1])==0 or (t[j-1][-1]!=(j if index_in_a else i))
					#	while 1:pass
					if len(t[j-1])==0 or (t[j-1][-1]!=(j if index_in_a else i)):
						t[j]=[]
						t[j].extend(t[j-1])
						t[j].append((j if index_in_a else i))
						lens[j]+=1
			elif lens[j-1]>lens[j]:
				t[j]=[]
				t[j].extend(t[j-1])
				lens[j]=lens[j-1]
	return t[-1]
def main():
	from time import time
	from random import randint
	a=[]
	for i in xrange(100):a.append(randint(0,26))
	b=[]
	for i in xrange(3):b.append(randint(0,26))
	#a="qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1cmihwerpty3497my5340cm2-9y25-1c9n5814c57n-5v81mc5m1-5v77nv-175n-1qwednnddniioqwehiqweho;cmihwerpty3497my53"
	#b="ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819ucv84-n13v74-1c1xmt7-,1,-x,y9-tzx-1,4zx=6vun4c9-n7-1nxc489-1cn751cn5-1c75n-91vb75-1bcnxm819"
	max=100
	#'''
	a=[]
	for i in xrange(1000):a.append(randint(0,26))
	b=[]
	for i in xrange(1000):b.append(randint(0,26))
	
	t0=time()
	for i in xrange(max):
		alpha=lcs(a,b)
	t0=time()-t0
	t1=time()
	for i in xrange(max):
		beta=lcs0(a,b)
	t1=time()-t1
	print t0
	print t1
	return
	#'''
	for i in xrange(max):
		len_a=randint(3,300)
		len_b=randint(3,300)
		a=[]
		for i in xrange(len_a):a.append(randint(0,26))
		b=[]
		for i in xrange(len_b):b.append(randint(0,26))
		if lcs(a,b)!=lcs0(a,b):
			print 'failed:'
			print a,b
			print lcs(a,b),lcs0(a,b)
	return
	max=100
	t0=time()
	for i in xrange(max):r0=lcs(a,b)
	t0=time()-t0
	print t0
	return
	import sys
	if len(sys.argv)!=2 or sys.argv[1]=='test':
		if len(sys.argv)==4:
			a=sys.argv[2]
			b=sys.argv[3]
		elif len(sys.argv)==3:
			a=sys.argv[1]
			b=sys.argv[2]
		else:
			a='agcga'
			b='cagatagag'
		print a,b
		x=lcs(a,b)
		print x
		print ''.join(map(lambda c0:a[c0],x))
		print '---'
		x=lcs_b(a,b)
		print x
		print ''.join(map(lambda c0:a[c0],x))
		return
	elif sys.argv[1]=='acc':
		alpha,beta=[],[]
		counter=0
		#while alpha==beta:
		word_len=3
		while len(alpha)==len(beta):
			a=[]
			for i in xrange(word_len):a.append(randint(0,26))
			b=[]
			for i in xrange(word_len):b.append(randint(0,26))
			alpha=lcs_c(a,b)
			alpha.sort()
			beta=lcs_b(a,b)
			beta.sort()
			counter+=1
			if counter%100000==0:
				word_len+=1
				print counter,word_len
		print a,b
		print '///'
		print alpha
		print '---'
		print beta
		return
	elif sys.argv[1]=='speed':
		a=[]
		for i in xrange(100):a.append(randint(0,26))
		b=[]
		for i in xrange(1000):b.append(randint(0,26))
		max=100
		t0=time()
		for i in xrange(max):r0=reduce(lambda x,y:x+str(a[y]),['']+lcs_b(a,b))
		t0=time()-t0
		
		t1=time()
		for i in xrange(max):r1=reduce(lambda x,y:x+str(a[y]),['']+lcs_c(a,b))
		t1=time()-t1
		print t0
		print t1
		if r0!=r1:print 'you seem to have failed:\n%s\n%s'%(r0,r1)
		return
	else:
		print 'args'
		return
	alpha=lcs(a,b)
	alpha.sort()
	beta=lcs_b(a,b)
	beta.sort()
	print alpha
	print '---'
	print beta
	if alpha!=beta:print 'you failed'
	#print lcs_b('agcga','cagatagag')
	return
	max=1
	
if __name__=='__main__':main()